package leetcode_链表;

import general_class.ListNode;

/**
 * 回文链表
 * 算法：链表
 *
 * @author origin
 */
public class _234 {

    public boolean isPalindrome_new(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast != null) slow = slow.next;
        slow = reverse(slow);
        while (head != null && slow != null) {
            if (head.val != slow.val) return false;
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

    ListNode reverse(ListNode head) {
        ListNode pre = null, next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    public boolean isPalindrome(ListNode head) {
        StringBuilder tem = new StringBuilder();
        while (head != null) {
            tem.append(head.val);
            head = head.next;
        }
        String s = tem.toString();
        String reverse = tem.reverse().toString();
        System.out.println(tem + "   " + reverse);
        return s.equals(reverse);
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, null)));
        new _234().isPalindrome(listNode);
    }
}
